// https://leetcode->cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 使用哈希表+双向链表实现LRU缓存
// 2. 哈希表提供O(1)查找，双向链表维护访问顺序
// 3. get操作将节点移到链表头部，put操作更新或淘汰尾部节点
// 4. 利用list::splice高效移动节点，避免内存分配
// 5. 时间复杂度：O(1)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <list>
#include <unordered_map>

class LRUCache 
{
private:
    typedef list<pair<int, int>>::iterator LTIter;
private:
    size_t _capacity;
    unordered_map<int, LTIter> _hashMap;
    list<pair<int, int>> _LRUList;
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {}
    
    int get(int key) 
    {
        auto ret = _hashMap.find(key);
        if (ret != _hashMap.end())
        {
            auto it = ret->second;
            _LRUList.splice(_LRUList.begin(), _LRUList, it);
            return it->second;
        }
        return -1;
    }
    
    void put(int key, int value) 
    {
        auto ret = _hashMap.find(key);
        if (ret == _hashMap.end())
        {
            if (_LRUList.size() == _capacity)
            {
                pair<int, int> back = _LRUList.back();
                _hashMap.erase(back.first);
                _LRUList.pop_back();
            }
            _LRUList.push_front(make_pair(key, value));
            _hashMap[key] = _LRUList.begin();
        }
        else
        {
            auto it = ret->second;
            it->second = value;
            _LRUList.splice(_LRUList.begin(), _LRUList, it);
        }
    }
};
int main()
{
    LRUCache* lRUCache = new LRUCache(2);
    lRUCache->put(1, 1); // 缓存是 {1=1}
    lRUCache->put(2, 2); // 缓存是 {1=1, 2=2}
    cout << lRUCache->get(1) << endl;    // 返回 1
    lRUCache->put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    cout << lRUCache->get(2) << endl;    // 返回 -1 (未找到)
    lRUCache->put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    cout << lRUCache->get(1) << endl;    // 返回 -1 (未找到)
    cout << lRUCache->get(3) << endl;    // 返回 3
    cout << lRUCache->get(4) << endl;    // 返回 4

    return 0;
}